<?php
/*
 * 给定两个单词beginWord和endWord，还有一本词典是list类型。
 * 找到所有从beginWord变到endWord的最短转换路径，变动的规则是：
 * 1，一次只能变一个位置的字符
 * 2，每一个转换后的word一定要在list中
 * 3，初始时list中没有beginWord这个词
 * 比如beginWord = "hit"
 * endWord = "cog"
 * wordList = ["hot","dot","dog","lot","log","cog"]
 * 返回：[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"]]
 *
 * 注意：
 * 1，返回值的类型为List<List<String>>
 * 2，如果不存在转化路径请返回空链表（不是null）
 * 3，所有的词一定都是相同长度的
 * 4，所有词都是小写的a~z
 * 5，在list中没有重复的词
 * 6，beginWord和endWord都不是空字符串或者null
 */

$begin    = 'hit';
$end      = 'cog';
$wordList = ["hot", "dot", "dog", "lot", "log", "cog"];
$obj      = new Code_03_WordLadder();
var_dump($obj->do($begin, $end, $wordList));

class Code_03_WordLadder
{
    public $res;

    public function do($begin, $end, $wordList)
    {
        $wordList[] = $begin;
        // 生成 word => 邻居list的hashMap
        $nextMap = $this->getWordNeighborMap($wordList);
        // 根据上面的邻居map生成 word => end要走的步数
        $distanceMap = $this->getWordDistanceMap($begin, $nextMap);
        // 根据邻居map和距离map，获取最短的单词变换路径
        $pathList = new SplDoublyLinkedList();
        $this->getShortestPath($begin, $end, $nextMap, $distanceMap, $pathList);
        return $this->res;
    }

    // 生成每个单词的邻居map，【如 hit => [hot]】
    public function getWordNeighborMap($wordList)
    {
        $map = [];
        for ($i = 0, $len = count($wordList); $i < $len; $i++) {
            // 所有单词的邻居列表（只改变一个字符的）
            $map[$wordList[$i]] = $this->getWordNeighbor($wordList[$i], $wordList);
        }
        return $map;
    }

    public function getWordNeighbor($word, $wordList)
    {
        $res = [];
//        $arr = str_split($word);
        for ($cur = ord('a'); $cur <= ord('z'); $cur++) {
            for ($i = 0, $len = strlen($word); $i < $len; $i++) {
                if ($word[$i] != chr($cur)) {
                    $tmp = $word[$i];
                    $word[$i] = chr($cur);
                    if (in_array($word, $wordList)) {
                        $res[] = $word;
                    }
                    $word[$i] = $tmp;
                }
            }
        }
        return $res;
    }

    // BFS来获取每个单词的深度
    public function getWordDistanceMap($word, $nextMap)
    {
        $distance = [];
        $distance[$word] = 0;
        $queue = new SplQueue();
        $queue->enqueue($word);
        $isVisited = [];
        $isVisited[] = $word;
        while (!$queue->isEmpty()) {
            $cur = $queue->dequeue();
            foreach ($nextMap[$cur] as $next) {
                if (!in_array($next, $isVisited)) {
                    $distance[$next] = $distance[$cur] + 1;
                    $queue->enqueue($next);
                    $isVisited[] = $next;
                }
            }
        }
        return $distance;
    }

    // 获取当前单词到end的最短路径
    public function getShortestPath($cur, $end, $nextMap, $distanceMap, $solution)
    {
        $solution->push($cur);
        if ($end == $cur) {
            $tmp = [];
            for ($i = 0; $i < $solution->count(); $i++) {
                $tmp[] = $solution->offsetGet($i);
            }
            $this->res[] = $tmp;
        } else {
            foreach ($nextMap[$cur] as $next) {
                if ($distanceMap[$next] == $distanceMap[$cur] + 1) {
                    $this->getShortestPath($next, $end, $nextMap, $distanceMap, $solution);
                }
            }
        }
        $solution->shift();
    }

}